/**
 * Program 12.7 BST-based symbol table
 * ------------------------------------------------------------------------------
 * The `STsearch` and `STinsert` functions in this implementation use the compact recursive functions `searchR`
 * and `insertR` that directly mirror the recursive definition of BSTs.
 *
 * The link `head` points to the root of the tree, and a tail node (z) is used to represent empty trees.
 */
#include <stdlib.h>

#include "Item.h"
#include "ST.h"
typedef struct STnode* link;

struct STnode {
    Item item;
    link l;
    link r;
    int N;
};

link head;
link z;

link NEW(Item item, link l, link r, int N) {
    link x = malloc(sizeof(*x));
    x->item = item;
    x->l = l;
    x->r = r;
    x->N = N;
    return x;
}

void STinit(int maxN) {
    z = NEW(NULLitem, 0, 0, 0);
    head = z;
}

int STcount() {
    return head->N;
}

// link insertR(link h, Item item) {
//     if (h == z) {
//         return NEW(item, z, z, 1);
//     }
//     Key v = key(item);
//     Key t = key(h->item);
//     if (less(v, t)) {
//         h->l = insertR(h->l, item);
//     }else {
//         h->r = insertR(h->r, item);
//     }
//     (h->N)++;
//     return h;
// }
//
// void STinsert(Item item) {
//     head = insertR(head, item);
// }

/**
 * Program 12.9 Insertion in BSTs (nonrecursive)
 * ----------------------------------------------------------------------------------------
 * Inserting an item into a BST is equivalent to doing an unsuccessful search for it,
 * then attaching a new node for the item in place of the null link where the search terminates.
 *
 * Attaching the new node requires that we keep track of the parent p of x as we proceed down the tree.
 * When we reach the bottom of the tree, p points to the node whose link we must change to
 * point to the new node inserted.
 *
 */
void STinsert(Item item) {
    if (head == z) {
        head = NEW(item, z, z, 1);
        return ;
    }
    link p = head;
    link x = p;
    Key v = key(item);
    while (x != z) {
        p = x;
        (x->N)++;
        if (less(v, key(x->item))) {
            x = x->l;
        }else {
            x = x->r;
        }
    }
    x = NEW(item, z, z, x->N);
    if (less(v, key(p->item))) {
        p->l = x;
    }else {
        p->r = x;
    }
}

Item searchR(link h, Key v) {
    if (h == z) {
        return NULLitem;
    }
    Key t = key(h->item);
    if (eq(v, t)) {
        return h->item;
    }
    if (less(v, t)) {
        return searchR(h->l, v);
    }else {
        return searchR(h->r, v);
    }
}

Item STsearch(Key v) {
    return searchR(head, v);
}

void STdelete(Item);

Item STselect(int);

/**
 * Program 12.8 Sorting with a BST
 * ----------------------------------------------------------------------------
 * An inorder traversal of a BST visits the items in order of their keys.
 * In this implementation, visit is a function supplied by the client
 * that is called with each of the items as its argument, in order of their keys.
 */
void sortR(link h, void (*visit)(Item)) {
    if (h == z) {
        return;
    }
    sortR(h->l, visit);
    visit(h->item);
    sortR(h->r, visit);
}


void STsort(void (*visit)(Item)) {
    sortR(head, visit);
}